package thired.class20_indextree;

public class Class02_IndexTree2D {
    public static class Index2Tree{
        private int[][] tree;
        int N;
        int M;

        public Index2Tree(int N,int M){
            this.N = N + 1;
            this.M = M + 1;
            tree = new int[N][M];
        }

        public int sum(int i,int j){
            int res = 0;
            for (int k = i; k > 0; k -= k &(-k)) {
                for (int l = j; l > 0 ; l -= l&(-l)) {
                    res += tree[k][l];
                }
            }
            return  res;
        }

        public void add (int i,int j,int c){
            for (int k = i; k < N ; k += k & (-k)) {
                for (int l = j; l < M; l += l &(-l)) {
                    tree[i][j] += c;
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            if (N == 0 || M == 0) {
                return 0;
            }
            return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
        }
    }


}
